package com.zjsru.plan2024.oneday;

import java.util.Arrays;

/**
 * 2580. 统计将重叠区间合并成组的方案数
 * @Author: cookLee
 * @Date: 2024-03-27
 */
public class CountWays {

    /**
     * 主
     * \
     * 输入：ranges = [[6,10],[5,15]]
     * 输出：2
     * 解释：
     * 两个区间有交集，所以它们必须在同一个组内。
     * 所以有两种方案：
     * - 将两个区间都放在第 1 个组中。
     * - 将两个区间都放在第 2 个组中。
     * \
     * 输入：ranges = [[1,3],[10,20],[2,5],[4,8]]
     * 输出：4
     * 解释：
     * 区间 [1,3] 和 [2,5] 有交集，所以它们必须在同一个组中。
     * 同理，区间 [2,5] 和 [4,8] 也有交集，所以它们也必须在同一个组中。
     * 所以总共有 4 种分组方案：
     * - 所有区间都在第 1 组。
     * - 所有区间都在第 2 组。
     * - 区间 [1,3] ，[2,5] 和 [4,8] 在第 1 个组中，[10,20] 在第 2 个组中。
     * - 区间 [1,3] ，[2,5] 和 [4,8] 在第 2 个组中，[10,20] 在第 1 个组中。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        CountWays countWays = new CountWays();
        int[][] ranges = new int[][]{{6,10},{5,15}};
        System.out.println(countWays.countWays(ranges));
    }

    private static final int MOD = 1000000007;

    /**
     * 计数方式
     *
     * @param ranges 范围
     * @return int
     */
    public int countWays(int[][] ranges) {
        //分组永远有一组可以实现
        int ans = 1;
        int len = ranges.length;
        //数组排序
        Arrays.sort(ranges);
        for (int i = 0; i < len; ) {
            int right = ranges[i][1];
            //扩展到下一个分组，直到下一个区间不再与之相交为止
            int j = i + 1;
            while (j < len && ranges[j][0] <= right) {
                right = Math.max(right, ranges[j][1]);
                j++;
            }
            //即是2的K次方 k为符合的条件组
            ans = ans * 2 % this.MOD;
            i = j;
        }
        return ans;
    }
}
